package com.fh.binarysearch;
// 33. 搜索旋转排序数组
class T33 {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止整数溢出
            
            // 如果中间元素正好是目标值，直接返回索引
            if (nums[mid] == target) {
                return mid;
            }
            
            // 判断左半部分 [left, mid] 是否有序
            if (nums[left] <= nums[mid]) {
                // 左半部分有序
                if (nums[left] <= target && target < nums[mid]) {
                    // 目标值在有序的左半部分内，缩小搜索范围到左半部分
                    right = mid - 1;
                } else {
                    // 目标值不在左半部分，转而搜索右半部分
                    left = mid + 1;
                }
            } else {
                // 右半部分 [mid, right] 有序
                if (nums[mid] < target && target <= nums[right]) {
                    // 目标值在有序的右半部分内，缩小搜索范围到右半部分
                    left = mid + 1;
                } else {
                    // 目标值不在右半部分，转而搜索左半部分
                    right = mid - 1;
                }
            }
        }
        
        // 未找到目标值
        return -1;
    }
}